﻿#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<string>
#include<vector>
using namespace std;
//33. 判断字符是否唯⼀（easy）
//bool isUnique(string astr)
//{
//    int bit = 0;
//    if (astr.size() > 26) return false;
//    for (auto e : astr)
//    {
//        int i = e - 'a';
//        if (bit&(1<<i)) return false;
//        bit = (bit) | (1 << i);
//    }
//    return true;
//}

//34.丢失的数字（easy）
// 
// 方法一：等差数列;
//class Solution {
//public:
//    int missingNumber(vector<int>& nums)
//    {
//        int sum = 0;
//        for (auto e : nums) sum += e;
//        int tmp = 0;
//        for (int i = 0; i <= nums.size(); i++) tmp += i;
//        return tmp - sum;
//    }
//};

//方法二：位运算;
//class Solution {
//public:
//    int missingNumber(vector<int>& nums)
//    {
//        int ret = 0;
//        for (auto e : nums) ret ^= e;
//        for (int i = 0; i <= nums.size(); i++) ret ^= i;
//        return ret;
//    }
//};


////////35.两整数之和（medium）
//class Solution {
//public:
//    int getSum(int a, int b)
//    {
//        while (b != 0)
//        {
//            int x = a ^ b;//无进位相加；
//            unsigned int  carry = (unsigned int)(a & b) << 1;
//            a = x;
//            b = carry;
//        }
//        return a;
//    }
//};

//36. 只出现⼀次的数字II（medium）
//int singleNumber(vector<int>& nums)
//{
//    int i = 0;
//    int ret = 0;
//    while (i < 32)
//    {
//        int tmp = 0;
//        for (int j = 0; j < nums.size(); j++)
//        {
//             tmp = (tmp + ((nums[j] >> i) & 1));
//        }
//        tmp %= 3;
//        ret +=(tmp << i);
//        i++;
//    }
//    return ret;
//}
//
//////////消失的数字III
//class Solution {
//public:
//    vector<int> singleNumber(vector<int>& nums)
//    {
//        int tmp = 0;
//        for (auto e : nums) tmp ^= e;
//        此时tmp结果为出现一次数字的异或;
//
//        int diff = 0; //寻找为1的比特位;
//        while (1)
//        {
//            if (((tmp >> diff) & 1) == 1) break;
//            diff++;
//        }
//        把数据分成两类，计算结果；
//        int a = 0, b = 0;
//        for (auto e : nums)
//        {
//            if (((e >> diff) & 1) == 0) a ^= e;
//            else b ^= e;
//        }
//        return { a,b };
//    }
//};
///////////37.消失的两个数字（hard）
//class Solution {
//public:
//    vector<int> missingTwo(vector<int>& nums)
//    {
//        int tmp = 0;
//        转换成消失的数字III
//        for (auto e : nums)  tmp ^= e;
//        for (int i = 0; i <= nums.size() + 2; i++) tmp ^= i;
//        此时tmp为消失的两数之异或;
//        int diff = 0;
//        while (1)
//        {
//            if (((tmp >> diff) & 1) == 1) break;
//            diff++;
//        }
//        开始分类；
//        int a = 0, b = 0;
//        for (auto e : nums)
//        {
//            if (((e >> diff) & 1) == 1)  b ^= e;
//            else  a ^= e;
//        }
//        for (int i = 0; i <= nums.size() + 2; i++)
//        {
//            if (((i >> diff) & 1) == 1)  b ^= i;
//            else  a ^= i;
//        }
//        return { a,b };
//    }
//};

string modifyString(string s)
{
    int tmp = 0;
    for (auto e : s) {
        if (e != '?') {
            tmp |= (1 << (e - 'a'));  // 用位运算标记出现的字母
        }
    }
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '?') {
            int j = 0;
            // 找出未使用的字母
            while ((tmp >> j) & 1) {
                ++j;
            }
            // 用未使用的字母替换 '?'，并更新 tmp
            s[i] = 'a' + j;
            tmp |= (1 << j);  // 标记该字母已经使用
        }
    }
    return s;
}
int main()
{
    string s{ "?zs" };
    cout << modifyString(s) << endl;
	return 0;
}